/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package item36;

import org.junit.Test;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:Convert.java v1.0 2018/8/12 上午1:19 LvJing Exp $
 */
public class Convert {

    /**
     * 题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
     * 中序遍历二叉树即可，最先遍历到的就是最小的，最后遍历的是最大的。
     */
    public class Solution {

        private TreeNode head;

        private TreeNode temp;

        public TreeNode Convert(TreeNode pRootOfTree) {
            if (pRootOfTree == null)
                return null;
            convertHelper(pRootOfTree);
            return head;
        }

        private void convertHelper(TreeNode currentNode) {
            if (currentNode == null)
                return;
            convertHelper(currentNode.left);

            if (head == null) {
                head = currentNode;
                temp = currentNode;
            } else {
                temp.right = currentNode;
                currentNode.left = temp;
                temp = currentNode;
            }

            convertHelper(currentNode.right);
        }
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    @Test
    public void test01() {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(8,
                new TreeNode(6, new TreeNode(5), new TreeNode(7)),
                new TreeNode(10, new TreeNode(9), new TreeNode(11)));
    }
}
